1. Field of the Invention
This invention relates generally to combinational and sequential logic networks and in particular to a method and means for predicting timing information for a mapped and optimized logic network using the unmapped logic network.
2. Prior Art
Typically, an automatic design system is used to convert a logic design into a specific logic circuit for an application specific integrated circuit (ASIC). However, prior to using the automated design system, a particular fabrication technology, sometimes referred to as the target technology, is selected for the ASIC. Usually, an ASIC manufacturer has a number of fabrication lines. Each fabrication line is a possible target technology. For example, a 2.0 micron complementary metal oxide semiconductor (CMOS) fabrication line may be a first target technology and a 0.5 micron CMOS fabrication line a second target technology. Other examples of target technologies include bipolar emitter coupled logic (ECL) fabrication lines and bipolar transistor-transistor logic (TTL) fabrication lines. For each fabrication line, the manufacturer typically provides a library of standard gates, also called gates, that must be used to implement the ASIC logic design for that particular fabrication line. Thus, selection of the fabrication line defines the library of standard gates that must be used to implement all user logic designs for that target technology.
Typically, an automated design system first converts Boolean logic equations or a description of a logic circuit in a hardware description language to an unmapped logic network, sometimes referred to herein as an unmapped logic circuit. In general terms, an unmapped logic network is a directed acyclic graph where (i) each node in the graph represents a signal in the circuit and has a logic function and (ii) each edge in the graph represents the direct signal dependencies. Moreover, the unmapped logic network is independent of any fabrication process. Specifically, the logic functions of the directed acyclic graph nodes are not specified in terms of the gates associated with a particular fabrication process.
A mapping and optimization means is used to convert the unmapped logic network to a mapped and optimized logic network consisting of interconnections of standard gates selected from the target technology library. The mapping and optimization means is typically chosen by the user.
In addition to the standard gates, most target technology libraries include information about the signal propagation delay, i.e., the time required for a signal change on a gate input line to travel through the gate to the gate output line. These time delays may be used to determine the time delay characteristics of the mapped logic network. Generally, the longer the signal propagation time through the logic network, i.e., the longer the delay time, the poorer the speed performance of the logic network and conversely.
The time delay of the mapped and optimized logic network is typically one of the performance parameters for the ASIC design. Other performance parameters include the size and the power consumption of the mapped and optimized logic network. Usually, the criteria used by the mapping and optimization means are a combination of these parameters, e.g., a minimum area circuit with a maximum time delay of ten nanoseconds (ns) and a power consumption of no more than one milliwatt.
For most user logic designs, speed optimization is a repetitive process that includes many changes to the logic network. Mapping the logic network after each change and using the target technology library time delay information to determine the time delay for the mapped logic network, while accurate, is not feasible in practice from a computer time standpoint.
The logic circuit speed optimization process can be significantly enhanced if the user has means to determine speed critical sections of the unmapped logic network, and uses these means to direct the optimization without iteratively mapping each change to determine the effect of the change on speed performance. Thus, different methods have been used to estimate the time delay associated with a mapped logic network using only the unmapped logic network. Unfortunately, the prior art methods for estimating mapped logic network time delays using an unmapped logic network have not been particularly successful.
For example, one of the most commonly used methods to estimate the mapped logic network time delay is to count the number of logic levels in the unmapped logic network. To determine the logic levels, a signal path is selected through the unmapped logic network. Each logic node in the signal path is a logic level. A logic node is sometimes a logic gate, buffer, and invertor and other times only each logic gate is considered a logic node.
A single constant time delay is assigned to every logic node in the signal path independent of the either the logic complexity of the logic node or the number of other logic nodes directly driven by that logic node. Therefore, the estimated time delay is a function of only the number of logic nodes. The only good feature of this model, referred to as the level model, is its simplicity. The level model fails to account for either the complexity of the logic function of the node or the number and complexity of other nodes driven by the node. The level model also fails to consider the effect of either the target technology or the mapping and optimization method on the mapped logic network time delay.
Various improvements to the level model have been attempted. In one improvement, referred to as the level-fanout model, a function of the fanout at a logic node is added to the constant time delay of the level model. Typically, the function is a linear function of the fanout at the logic node. As used herein, fanout is the number of input lines driven by the signal on the output line of a logic node.
In general, the methods used to estimate time delay using unmapped logic networks have several shortcomings. First, the methods fail to account for the complexity at a given logic node. Second, the methods fail to account for the fanout capacitance at a logic node. The level-fanout method attempts to capture some fanout information, but this method evaluates neither the slope of the linear function nor the relative importance of the slope to the constant time delay. Third, the actual time delay for a mapped logic network is dependent upon the characteristics of the mapping and optimization method. Fourth, the methods fail to account for the target technology. The actual time delay parameters for a mapped logic network vary greatly from target technology to target technology. Fifth and finally, since these methods fail to account for either the mapping and optimization method or the target technology, the time delays are at best relative measures, which can only be used for comparisons with each other and have no meaningful absolute value for the time delay. As used herein, "absolute value" for the time delay means an approximation of the actual delay time associated with the mapped and optimized logic network in the target technology as opposed to a "relative value" measure.
Thus, a method for generating accurate time delay estimates after mapping for a specified target technology must account for (i) the actual time delays in the mapped logic network that depend on the choice of target technology and (ii) the actual time delays that depend on the chosen mapping and optimization method. If the method does not account for these time delays, the method cannot be used to obtain absolute time delay values. A method for estimating mapped logic network time delays that included both target technology time delay characteristics and mapping and optimization time delay characteristics would represent a significant new tool for computer aided logic design.